package com.du.algorithm.primary.util;

/**
 * @Desc :
 * @Author: shuangdu
 * @date : 2023/1/11
 */
public class SortUtil {

    private SortUtil(){}

    /**
     * 快排
     * @param arr
     */
    public static void fastSort(int[] arr) {
        partationArr(arr, 0, arr.length - 1);
    }

    private static void partationArr(int[] arr, int start, int end) {
        if (start < 0 || start > end || end > arr.length) return;
        int first = start;
        int second = start;
        while (second != end) {
            if (arr[second] <= arr[end]) {
               swap(arr, first, second);
               first++;
            }
            second++;
        }

        swap(arr, first, end);

        partationArr(arr, start, first - 1);
        partationArr(arr, first + 1, end);
    }

    /**
     * 数组交换下标位置
     * @param arr
     * @param s
     * @param t
     */
    public static void swap(int[] arr, int s, int t) {
        int temp = arr[s];
        arr[s] = arr[t];
        arr[t] = temp;
    }
}
